I. Field of the Invention
The embodiments described herein are related to Low-Density Parity-Check coding and decoding.
II. Description of the Related Art
Low-density parity-check (LDPC) codes are linear block codes that employ a sparse (i.e., low-density) parity-check matrix. The parity check matrix comprises element values of 1 and 0, and is considered sparse if there are few 1's in each row and column. For example, in a sparse n×m parity check matrix, wc<<n and wr<<m, where wc is the number of 1's in each column and wr is the number of 1's in each row.
Tanner graphs, which are bipartite graphs, are commonly used to represent LDPC codes. A Tanner graph comprises n variable nodes and m check nodes, and connections (i.e., edges) between the variable and check nodes correspond to 1-values in the n×m parity check matrix. For example, matrix element hij=1 indicates that the jth check node is connected to the ith variable node.
Decoding algorithms configured for LDPC codes typically employ iterative procedures, such as the message-passing algorithm. An initial step comprises tentatively setting the variable data bits to the received data-bit values and sending those values to the check nodes. This is followed by a second step in which each check node calculates response messages using the variable data bit values received from multiple variable nodes. to be sent back to each variable node.
During the second step, an ith check node calculates a response message for a jth variable node by employing only the received data-bit values from the other variable nodes to which it is connected and using those values in a parity-check equation to determine what the jth variable node's data-bit value should be. The ith check node similarly calculates specific response messages for its other associated variable nodes. The ith check node transmits a response message to each of its associated variable nodes.
At the beginning of a third step, the jth variable node receives the response message from the ith check node and at least one additional check-node response message from another check node. It then uses these response messages (i.e., suggestions) and its original received data-bit value in a decision process to update its estimated data-bit value. A subsequent iteration begins when the variable nodes send their updated data-bit values to their respective check nodes.
Decoding is typically a highly computationally complex process. Techniques for reducing computational complexity result in other significant obstacles, including increased memory requirements and interconnection complexity.